|
The top-nodes algorithm is an algorithm for managing a resource reservation calendar.〔(Related US patent )〕 It is used when a resource is shared among lots of users (for example bandwidth in a telecommunication link, or disk capacity in a large data center). The algorithm allows * to check if an amount of resource is available during a specific period of time, * to reserve an amount of resource for a specific period of time, * to delete a previous reservation, * to move the calendar forward (the calendar covers a defined duration, and it must be moved forward as time goes by). ==Principle== The calendar is stored as a binary tree where leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants. The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time. A node of the binary tree is a "top-node" for a given reservation if * all its descendants are inside the reservation period of time, and * it is the root node, or at least one descendant of the parent node is outside of the reservation period of time. The following value is stored in each node: q(node) = max(q(left child), q(right child)) + total amount of reserved resource for all reservations having this node as a "top-node" (for code optimization, the two parts of this sum are usually stored separately.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Top-nodes algorithm」の詳細全文を読む スポンサード リンク
|
